Wireless Sensor Networks (WSN) use low-bandwidth radios to create a self-healing wireless mesh network. In WSN networks, nodes route data to a centralized point in the network referred to as a base station. Periodically each node shares its local neighborhood link information with the rest of the network. Each node uses this distributed link information to find the best path from itself to the base station. Data is then sent along this optimal path.
Most WSN mesh algorithms use single-path routing algorithms similar to algorithms commonly found in wired networks. These conventional algorithms are commonly adapted to take advantage of the wireless nature of the network by “overhearing” neighbor traffic to form detailed link estimates. These detailed link estimates are used to form an optimal single-path route to the base station. Wireless mesh networks of this type are described in the literature (see, for example, U.S. patent application Ser. No. 11/433,194).
Wireless link quality is known to vary over time. Since paths are formed on the basis of link quality estimates (or hop ‘cost’), mesh algorithms must periodically use energy to recalculate the best path at the lowest hop cost to the base station. If the period between recalculations of the optimal path is too long, nodes may use bad paths. If the period used is short, the network will drain available energy (usually battery power) rapidly. Since the variation of link quality over time is difficult to determine, most algorithms choose a single network-wide period based on network lifetime. In most cases, if a path goes bad between update periods, the data sent along that path is lost.
Different solutions have been proposed for overcoming data loss due to poor path quality. The most widely used solution is packet retransmission. If a packet is unable to be sent over a path, then the packet is resent until it is received by the next node along a path to the base station. Most wired protocols like TCP use an end-to-end retransmission strategy. The sending node continually resends to the receiving node until an acknowledgement of receipt is delivered. However, a difficulty associated with end-to-end recovery along a single path is the unreliable characteristics of the wireless communication link. The error accumulates exponentially over multiple hops from link to link, causing a high probability of packet loss, as illustrated in the graph of FIG. 1.
This graph indicates the limitation of the end-to-end retransmission scheme. As the number of hops increases, even networks with good link quality have a lower probability of delivering data packets to a base station.
One known modification of the single-path routing introduces a link by link retry to the end to end retry. Forwarding nodes resend data to the parent until the parent acknowledges receipt of the packet. By retransmitting at the link level, the link quality is artificially improved at each hop. However, as the number of hops increases along the path, even a set of good quality links has a low probability of delivering data reliably, as illustrated in the graph in FIG. 2.
This graph illustrates the number of retransmissions required to make a poor link into a high quality link. However, even after 8 retransmissions, such link-level retransmission scheme cannot make a poor-quality link into a high-quality link, and there is still possibility for data to be lost over the path.
Another known modification of the single-path routing may be implemented in systems where delay in delivery of data packets is acceptable. Packets which were to be dropped due to poor path quality, can be stored locally until a better path is found. Thus, data is stored either at the originating node or the forwarding node, until a good path is found, at which time the packet is forwarded.
A Delay Tolerant Network (DTN) is an appropriate solution for data which can be stored and retrieved at a later time. However, in networks where data is time-sensitive and must be delivered by a hard deadline, storage for a later date is inappropriate.
For time-sensitive data to be delivered over a single-path mesh network, DTN is an inappropriate solution and an alternative is to then fall back to using retransmissions in order to force the data to the base station hop by hop, expending large amounts of energy.
However, even packet retransmissions have limitations. Long-hop networks and/or networks where link quality can become excessively poor can still lose data along poor quality paths while expending large amounts of energy.
In addition, retransmissions have a detrimental consequence in high density networks. Due to the low-bandwidth radios used at each node, retransmissions can saturate the bandwidth, causing congestion. Congestion decreases the link quality on all surrounding paths with the consequence that all paths within radio distance of the retransmitting node will also begin dropping packets, and this can lead to a full network collapse.